class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

public class Solution {
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode head = new ListNode(0);
        ListNode tail = head;
        if (lists.length == 0) {
            return null;
        } else if (lists.length == 1){
            return lists[0];
        } else {
            for (int i = 1; i < lists.length; i++) {
                while (lists[0] != null && lists[i] != null) {
                    if (lists[0].val <= lists[i].val) {
                        tail.next = lists[0];
                        tail = tail.next;
                        lists[0] = lists[0].next;
                    } else {
                        tail.next = lists[i];
                        tail = tail.next;
                        lists[i] = lists[i].next;
                    }
                }
                tail.next = lists[0] != null ? lists[0] : lists[i];
                lists[0] = head.next;
                tail = head;
            }
            return head.next;
        }
    }
}
